#ifndef QUOTIENT_REMAINDER_H
#define QUOTIENT_REMAINDER_H
#include <utility>
#include <cassert>
#include "remainder.h"

template<typename T, typename N>
std::pair<N,T> quotient_remainder_nonnegative_recursive(T a, T b)
{
	assert(a >= 0 && b > 0);
	if (a < b) 
		return std::pair<N,T>(0,a);
	if (a - b < b) 
		return std::pair<N,T>(1,a-b);
	else {
		std::pair<N,T> q = quotient_remainder_nonnegative_recursive<N,T>(a, b + b);
		N m = q.first + q.first;
		a = q.second;
		if (a < b)
			return std::pair<N,T>(m,a);
		else
			return std::pair<N,T>(++m,a-b);
	}
}

template<typename T, typename N>
std::pair<N,T> quotient_remainder_nonnegative_iterative(T a, T b)
{
	if (a < b) return std::pair<N,T>(0,a);
	T c = largest_doubling(a,b);
	a = a - c;
	N n(1);
	while (c != b) {
		n *= 2;
		c /= 2;
		if (c <= a) {
			a = a - c;
			++n;
		}
	}
	return std::pair<N,T>(n,a);
}

template<typename Op, typename T, typename N>
std::pair<N,T> quotient_remainder(T a, T b, Op quo_rem)
{
	assert(b != T(0));
	std::pair<N,T> q_r;
	if (a < T(0)) {
		if (b < T(0)) {
			q_r = quo_rem(-a,-b);
			q_r.second = -q_r.second;
		}
		else {
			q_r = quo_rem(-a,b);
			if (q_r.second != T(0) ) {
				q_r.second = b - q_r.second;
				++q_r.first;
			}
			q_r.first = -q_r.first;
		}
	}
	else {
		if (b < T(0)) {
			q_r = quo_rem(a,-b);
			if (q_r.second != T(0) ) {
				q_r.second = b + q_r.second;
				++q_r.first;
			}
			q_r.first = -q_r.first;
		}
		else {
			q_r = quo_rem(a,b);
		}
	}
	return q_r;
}

#endif